#include <bits/stdc++.h>
using namespace std;

#define MAXN 805

const int INF = 0x3fffffff;

int g[MAXN][MAXN], nx, ny, match;

int slack[MAXN], lx[MAXN], ly[MAXN], fx[MAXN], fy[MAXN], sx[MAXN], sy[MAXN];

int T, N, a[MAXN], b[MAXN];

struct Node {
	int a, b;
	bool operator < (const Node &next) {
		return b < next.b;
	}
} p[MAXN];

int path(int u) {
	sx[u] = 1;
	for (int v = 1; v <= ny; v ++) {
		if (sy[v]) continue;
		if (g[u][v] == lx[u] + ly[v]) {
			sy[v] = 1;
			if (!fy[v] || path(fy[v])) {
				fx[u] = v; fy[v] = u;
				return 1;
			}
		} else {
			slack[v] = (slack[v] < (lx[u] + ly[v] - g[u][v])) ? slack[v] : (lx[u] + ly[v] - g[u][v]);
		}
	}
	return 0;
}

int km() {
	match = 0;
	memset(fx, 0, sizeof(fx));
	memset(fy, 0, sizeof(fy));
	for (int i = 1; i <= nx; i ++) {
		lx[i] = - INF;
		for (int j = 1; j <= ny; j ++) {
			lx[i] = (lx[i] < g[i][j]) ? g[i][j] : lx[i];
		}
	}
	for (int i = 1; i <= nx; i ++) {
		if (!fx[i]) {
			for (int j = 1; j <= ny; j ++) slack[j] = INF;
			memset(sx, 0, sizeof(sx));
			memset(sy, 0, sizeof(sy));
			while (!path(i)) {
				int p = INF;
				for (int j = 1; j <= ny; j ++) {
					if (!sy[j] && p > slack[j]) p = slack[j];
				}
				for (int j = 1; j <= nx; j ++) if (sx[j]) lx[j] -= p, sx[j] = 0;
				for (int j = 1; j <= ny; j ++) if (sy[j]) ly[j] += p, sy[j] = 0;
			}
		}
	}
	for (int i = 1; i <= ny; i ++) {
		match += g[fy[i]][i];
	}
	return match;
}
const int BZ = 20 * (1 << 20);
char Buf[BZ + 1], *buf = Buf;

template <class T>
inline void scan(T &a) {
	for (a = 0; *buf < '0' || *buf > '9'; ++buf);
	while (*buf >= '0' && *buf <= '9') {
		a = a * 10 + (*buf - '0');
		++buf;
	}
}
void work() {
	//scanf("%d", &N);
	scan(N);
	for (int i = 1; i <= N; i ++) {
		//scanf("%d %d", &a[i], &b[i]);
		scan(a[i]);
		scan(b[i]);
		p[i].a = a[i];
		p[i].b = b[i];
	}
	sort(p + 1, p + 1 + N);
	memset(g, 0, sizeof(g));
	for (int i = 1; i <= N; i ++) {
		for (int j = i + 1; j <= N; j ++) {
			g[j][i] = g[i][j] = p[i].a;
		}
	}
	nx = ny = N;
	int ans = km() / 2;
	printf("%d\n", ans);
}

int main() {
#ifdef __SKT__
	freopen("in", "r", stdin);
#endif
	fread(Buf, 1, BZ, stdin);
	//scanf("%d", &T);
	scan(T);
	while (T --) {
		work();
	}
	return 0;
}
